﻿#define _CRT_SECURE_NO_WARNINGS 1
class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) // 固定数 a
        {
            // 利⽤ 三数之和
            for (int j = i + 1; j < n; ) // 固定数 b
            {
                // 双指针
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum < aim) left++;
                    else if (sum > aim) right--;
                    else
                    {
                        ret.push_back({ nums[i], nums[j], nums[left++],
                       nums[right--] });
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> target;
        for (int i = nums.size() - 1; i > 1;)
        {
            if (nums[i] < 0) break;
            int left = 0, right = i - 1, temp = -nums[i];
            while (left < right)
            {
                int n = nums[left] + nums[right];
                if (n < temp)  left++;
                else if (n > temp) right--;
                else
                {
                    target.push_back({ nums[left],nums[right],nums[i] });
                    left++, right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            i--;
            if (i > 1 && nums[i] == nums[i + 1]) i--;
        }
        return target;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int k)
    {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int n = nums[left] + nums[right];
            if (n < k)
                left++;
            else if (n > k)
                right--;
            else
                return { nums[left],nums[right] };
        }
        return { -1 , -1 };
    }
};

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = 0;
        for (int i = nums.size() - 1; i > 1; i--)
        {
            int left = 0, right = i - 1;
            while (left < right)
            {
                int s = nums[left] + nums[right];
                if (s > nums[i]) {
                    n += right - left;
                    right--;
                }
                else
                    left++;
            }
        }
        return n;
    }
};

class Solution {
public:
    bool commpare(int a, int b) { return a > b; }
    int maxArea(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int maxN = 0;
        while (left < right)
        {
            int l = right - left;
            int v = 0;
            if (commpare(height[right], height[left]))
                v = height[left++] * l;
            else
                v = height[right--] * l;
            if (commpare(v, maxN))
                maxN = v;

        }
        return maxN;
    }
};